O problema de alocação de berços: um estudo das heurísticas simulated annealing e algoritmo genético

Este trabalho apresenta um estudo de caso das heurísticas Simulated Annealing e Algoritmo Genético para um problema de grande relevância encontrado no sistema portuário, o Problema de Alocação em Berços. Esse problema aborda a programação e a alocação de navios às áreas de atracação ao longo de um cais. A modelagem utilizada nesta pesquisa é apresentada por Mauri (2008) [28] que trata do problema como uma Problema de Roteamento de Veículos com Múltiplas Garagens e sem Janelas de Tempo. Foi desenvolvido um ambiente apropriado para testes de simulação, onde o cenário de análise foi constituido a partir de situações reais encontradas na programação de navios de um terminal de contêineres. Os testes computacionais realizados mostram a performance das heurísticas em relação a função objetivo e o tempo computacional, a m de avaliar qual das técnicas apresenta melhores resultados.

Uma metodologia heurística para minimizar o roteiro nos serviços de leitura de hidrômetros

Este trabalho tem por objetivo propor uma metodologia heurística para o Problema de Cobertura de Arcos aplicado aos serviços de saneamento, em específico na leitura de hidrômetros. Dentro deste contexto desenvolveu-se um aplicativo que permite o planejamento de rotas de maneira que os custos em distância percorrida sejam reduzidos e mantenham-se aproximadamente os mesmos em todos os percursos. A metodologia foi dividida em etapas. Na primeira etapa, para compreender melhor o problema, fez-se uma pesquisa de campo organizando os dados disponibilizados por uma empresa de saneamento. A segunda etapa foi caracterizada pela determinação de pontos em cada metade de trechos de quadra e nas interseções de ruas, os quais foram cadastrados, em um mapa georeferenciado. Este mapa contemplou a região escolhida para o estudo e os pontos cadastrados serviram para determinar e consequentemente, designar as medianas relacionadas, o que constitui a terceira etapa. Para isso utilizou-se respectivamente o algoritmo de Teitz Bart Modificado por CADP e o algoritmo de designação de Gillet e Johnson adaptado. Ao final desta etapa formaram-se subsetores dentro de um setor específico. Na última etapa encontrou-se as rotas de cada subsetor através do algoritmo genético. O aplicativo desenvolvido permitiu flexibilidade de ações, dando autonomia para o usuário na escolha das opções de cálculo. Sua interface gráfica possibilitou a elaboração de mapas e a visualização das rotas em cada subsetor. Além disso o aplicativo minimizou os percursos e distribuiu os subsetores com distâncias aproximadas. A eficiência das heurísticas que embasaram o aplicativo desenvolvido, foi comprovada através dos testes realizados, os quais obtiveram resultados de boa qualidade.

Uma abordagem evolucionária para o planejamento online de rotas para múltiplos robôs móveis em ambiente multiagente

O problema de planejamento de rotas de robôs móveis consiste em determinar a melhor rota para um robô, em um ambiente estático e/ou dinâmico, que seja capaz de deslocá-lo de um ponto inicial até e um ponto final, também em conhecido como estado objetivo. O presente trabalho emprega o uso de uma abordagem baseada em Algoritmos Genéticos para o planejamento de rotas de múltiplos robôs em um ambiente complexo composto por obstáculos fixos e obstáculos moveis. Através da implementação do modelo no software do NetLogo, uma ferramenta utilizada em simulações de aplicações multiagentes, possibilitou-se a modelagem de robôs e obstáculos presentes no ambiente como agentes interativos, viabilizando assim o desenvolvimento de processos de detecção e desvio de obstáculos. A abordagem empregada busca pela melhor rota para robôs e apresenta um modelo composto pelos operadores básicos de reprodução e mutação, acrescido de um novo operador duplo de refinamento capaz de aperfeiçoar as melhores soluções encontradas através da eliminação de movimentos inúteis. Além disso, o calculo da rota de cada robô adota um método de geração de subtrechos, ou seja, não calcula apenas uma unica rota que conecta os pontos inicial e final do cenário, mas sim várias pequenas subrotas que conectadas formam um caminho único capaz de levar o robô ao estado objetivo. Neste trabalho foram desenvolvidos dois cenários, para avaliação da sua escalabilidade: o primeiro consiste em um cenário simples composto apenas por um robô, um obstáculo movel e alguns obstáculos fixos; já o segundo, apresenta um cenário mais robusto, mais amplo, composto por múltiplos robôs e diversos obstáculos fixos e moveis. Ao final, testes de desempenho comparativos foram efetuados entre a abordagem baseada em Algoritmos Genéticos e o Algoritmo A*. Como critério de comparação foi utilizado o tamanho das rotas obtidas nas vinte simulações executadas em cada abordagem. A analise dos resultados foi especificada através do Teste t de Student.